// https://www.lintcode.com/problem/graph-valid-tree/description

// 如果只有一个连通块，并且边数n-1，一定没有环
// // 法一：并查集

// class Solution {
// public:
//     /**
//      * @param n: An integer
//      * @param edges: a list of undirected edges
//      * @return: true if it's a valid tree, or false
//      */
//     int* father;
//     int cnt;
//     int find(int a)
//     {
//         int x = a;
//         while (father[a] != a)
//         {
//             a = father[a];
//         }
//         while (x != a)
//         {
//             int tmp = father[x];
//             father[x] = a;
//             x = tmp;
//         }
//         return a;
//     }
//     void connect(int a, int b)
//     {
//         int fa = father[a];
//         int fb = father[b];
//         if (fa != fb)
//         {
//             father[fa] = fb;
//             cnt--;
//         }
//     }
    
//     bool validTree(int n, vector<vector<int>> &edges) {
//         if (edges.size() != n - 1)
//             return false;
//         father = new int[n];
//         cnt = n;
//         for (int i = 0; i < n; ++i)
//         {
//             father[i] = i;
//         }
//         for (int i = 0; i < n - 1; ++i)
//         {
    // Input
    // 10
    // [[0,1],[5,6],[6,7],[9,0],[3,7],[4,8],[1,8],[5,2],[5,3]]
    // Output
    // true
    // Expected
    // false
//             if (find(edges[i][0]) == find(edges[i][1])) // 重要
//                 return false;
//             connect(edges[i][0], edges[i][1]);
//         }
//         return cnt == 1;
//     }
// };


// // 法二：bfs

// 错的，无向图，不能这么搞，pair的左边不代表父节点
// 8
// [[0,1],[1,2],[3,2],[4,3],[4,5],[5,6],[6,7]]
// Output
// false
// Expected
// true
// class Solution {
// public:
//     bool validTree(int n, vector<vector<int>> &edges) {
//         if (edges.size() != n - 1)
//             return false;
//         queue<int> q;
//         map<int, vector<int>> nodes;
//         vector<int> rec(n, 0);
//         set<int> visited;
//         for (int i = 0; i < edges.size(); ++i)
//         {
//             nodes[edges[i][0]].push_back(edges[i][1]);
//             rec[edges[i][1]]++;
//         }
//         for (int i = 0; i < n; ++i)
//         {
//             if (rec[i] == 0)
//             {
//                 q.push(i);
//                 visited.insert(i);
//             }
//         }
//         while (!q.empty())
//         {
//             int tmp = q.front();
//             q.pop();
            
//             for (int i = 0; i < nodes[tmp].size(); ++i)
//             {
//                 if (visited.find(nodes[tmp][i]) != visited.end())
//                     return false;
//                 q.push(nodes[tmp][i]);
//                 visited.insert(nodes[tmp][i]);
//             }
//         }
//         return visited.size() == n;
//     }
// };

class Solution {
public:
    bool validTree(int n, vector<vector<int>> &edges) {
        vector<unordered_set<int>> g(n, unordered_set<int>());
        set<int> v;
        queue<int> q;
        q.push(0);
        v.insert(0);
        for (auto a : edges) {
            g[a[0]].insert(a[1]);
            g[a[1]].insert(a[0]);
        }
        while (!q.empty())
        {
            int tmp = q.front();
            q.pop();
            for (auto ttmp: g[tmp])
            {
                if (v.find(ttmp) != v.end())
                    return false;
                v.insert(ttmp);
                q.push(ttmp);
                g[ttmp].erase(tmp); //重要
            }
        }
        return v.size() == n;
    }
};